/*
 * @lc app=leetcode id=17 lang=cpp
 *
 * [17] Letter Combinations of a Phone Number
 */
class Solution {
private:
    unordered_map<char, string> map;

public:
    Solution() {
        map[2] = "abc";
        map[3] = "def";
        map[4] = "ghi";
        map[5] = "jkl";
        map[6] = "mno";
        map[7] = "pqrs";
        map[8] = "tuv";
        map[9] = "wxyz";
    }


    vector<string> letterCombinations(string digits) {
        vector<string> ret;
        int len = digits.size();
        if (len < 1) {
            return ret;
        }

        vector<string> slices;
        for (auto c : digits) {
            if (c >= '2' && c <= '9') {
                slices.push_back(map[c-'0']);
            }
        }

        string path;
        dfs(slices, 0, path, ret);
        return ret;
    }

    void dfs(vector<string>& slices, int pos, string& path, vector<string>& ret) { 
        if (pos == slices.size()) {
            ret.push_back(path);
            return;
        }

        for (auto c : slices[pos]) {
            path.push_back(c);
            dfs(slices, pos+1, path, ret);
            path.pop_back();
        }

    }
};

